package leetcode.treeCode.week3.leetcode_113;

import java.util.ArrayList;
import java.util.List;

class Solution {


    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ArrayList<Integer> path = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        dfs (root , targetSum , path , ans);
        return ans ;
    }
    private void dfs (TreeNode node ,int target , ArrayList<Integer> path , List<List<Integer>> ans){
        path.add(node.val);
        if (node.left == null && node.right == null){
            if (target == node.val){
                ans.add(new ArrayList<>(path));
            }
        }
        if (node.left != null){
            dfs (node.left , target - node.val , path , ans);
        }
        if (node.right != null){
            dfs (node.right , target - node.val , path , ans);
        }
        path.remove(path.size() -1);
    }
}